The present invention relates to a method and circuit for controlling access to memory cells of a data store which is accessed via a bus system with separate address and data phases.
Such known methods are used, for example, when the bus used is a so-called SP bus (split transaction bus), such as that described in the book by J. Hennessy and M. Kaufmann xe2x80x9cComputer Architecturexe2x80x9d, 2nd edition 1996, p. 439 and pp. 728-30. In an SP bus, access operations to the data store are subdivided into a number of phases. In particular, such phases include an address phase in which the address of a memory cell is transmitted on the bus, an evaluation phase possible for examining whether the address has been transmitted correctly, and a data phase in which data is transmitted on the bus to or from the data store. Subdivision into different phases is done to prevent the bus from becoming blocked between the address being provided and the associated data being provided. The different phases are allocated a common identifier (tag) which ensures that access operations with other identifiers also can be processed simultaneously and a data transfer phase can be allocated to an address phase.
Simultaneous processing of procedures with different identifiers, however, demands that certain requirements regarding the sequence in which the different procedures are processed be met (strong ordering). For example, a read procedure which started to be processed after a write procedure should be guaranteed not to overtake this write procedure. Otherwise, this would result in an incorrect value being read from the data store.
The data stores used are preferably high-speed semiconductor random access memories (RAM). However, this does not rule out application to other write/read memories, hard disks and other storage media. The method and the circuit are preferably used in data processing units with a number of processors and a common memory, which involve simultaneous access to the same memory cell. This does not rule out application to data processing units with only one arithmetical processor, however because a bus system of this generic type can be used in one of these data processing units as well.
In previous methods, an access operation to the data store is aborted as soon as the system recognizes that the necessary sequence for processing access operations has been violated. The respective processor is informed on the bus that the access attempt has not been successful. This means that this or another processor needs to try again later to carry out the access operation.
A disadvantage of the known method is that repeated access attempts place more stringent demands on the bus than are necessary. Furthermore, additional computation time is used up in the processor when access operations are repeated.
An object of the present invention therefore is to control overlapping memory access operations such that dependencies are taken into account without aborting the memory access operations in doing so.
The present invention is based on the realization that, compared with aborting an access operation, delaying the access operation produces better results because the resultant delays are ultimately shorter and take up less computation time than repeating the access operation.
The present invention involves comparing each of the address words in an address store with an address word newly transmitted on the bus. In this respect, the selection of the address words depends on the criteria selected when the sequence of the access operations to the data store is monitored. If the intention is to prevent read access operations from overtaking write access operations, for example, then the address words that belong to write access operations are selected. If only address words for write access operations are present in the address store in this case, then the selection involves all the address words in the address store.
The comparison results are entered in bit positions of a dependency vector, wherein each bit position is allocated to the identifier for the stored address word used in the respective individual comparison. The dependency vector produced is itself allocated the identifier for the new address word. The dependency vectors currently being processed are stored in a dependency vector store so that the similarities established in the comparison can be used for further processing. The similarities ultimately can be attributed to dependencies of the access operations characterized by the different identifiers. These involve time dependency when carrying out the access operations, the essence of this dependency being that the marked access operations absolutely must be completed beforehand.
A data phase being executed on the SP bus and allocated to an address by the identifier informs the control part that an access operation for this identifier has been completed. The control part subsequently deletes, in all dependency vectors, entries in the bit position allocated to this identifier. This means that, with the present invention, the correlations established in the comparison are matched to the instantaneous processing status as a result of the entries in the dependency vectors constantly being corrected.
The allocation of identifiers to address words and to the dependency vectors may be explicit or, as with the address words for example, may be achieved by always storing address words for a particular identifier at the same position in the address store. Similarly, identifiers may be allocated to dependency vectors in that each memory cell identifies the dependency vector which it contains when the dependency vectors are stored in a dependency vector store.
If, at least in the case of read access operations to the data store, a status signal is produced from the dependency vector whose identifier corresponds to the identifier for the address word for the respective read access operation, then it is possible for the access operation to the data store to be delayed until the status signal indicates that the relevant dependency vector contains no other entries. No entry means that there is no other dependency on other access operations which are to be carried out beforehand. Hence, the access operation can be carried out only if the criteria drawn up for the access sequence are met.
By virtue of the present invention, an address word is transmitted on the bus only once. If a conflict arises between different access operations, the access operation which is respectively last is delayed until the conflict has been resolved. Only then is the data word associated with the address word processed. In contrast to known methods, use of the bus is reduced because an access operation requires the address word to be transmitted only once. In addition, the processor that transmits the address word is relieved because repeated transmission of the address word is avoided. Finally, the present invention provides an access-control method which, despite the delays produced, causes the speed of access to be increased because the delays produced are shorter than the time which would be required to repeat the access operation.
In another, the embodiment invention relates to a circuit which is particularly suited to carrying out the access-control method. The characteristics described also apply to this circuit accordingly.
Hence, the present invention relates to a dependency controller and method for overlapping memory access operations whose addresses carry an identifier, in which controller the addresses which have not yet been processed are stored under the identifier and a comparison of each new address with stored addresses is used to produce and store a bit vector whose bits are allocated to the identifiers and are deleted when the allocated memory access operation has been completed.